package com.techyuan.algorithm.sorts;

/**
 * Created by tianjuntao on 2016/12/8.
 */
public class RadixSort implements ISort {
    int max;

    public RadixSort(int max) {
        this.max = max;
    }

    public int[] sort(int[] sortingArr) {
        return radixSort(sortingArr, String.valueOf(max).length());
    }

    /**
     * 将对应位按计数排序来一次排序各列
     * 可优化内存使用空间,多次计数排序的排序数组和待排序数组可以交换使用
     *
     * @param data
     * @param digit
     * @return
     */
    private int[] radixSort(int[] data, int digit) {
        CountingSort countingSort = new CountingSort(max);
        int[] tmpSortedArr = data;
        for (int i = 0; i < digit; i++) {
            final int tmpD = i;
            tmpSortedArr = countingSort.commonCountingSort(tmpSortedArr, 2000, new CountingSort.ArrItemNumGetter() {
                public Integer getItem(int[] arr, int index) {
                    return getdigit(arr[index], tmpD);
                }

                int getdigit(int x, int d) {
                    return ((x / (int) Math.pow(10.0, d)) % 10);    //确定桶号
                }
            });
        }

        return tmpSortedArr;
    }


}
